#include<stdio.h>

struct Node{
    int data;
    Node *next;
    Node(int x) : data(x) , next(NULL) {};
};

Node* head=new Node(5);

Node* reNode(Node* head);
Node* swapNode(Node* head);
void reorderNode(Node* head);

int main() {
    Node* n;
    n = reNode(head);
    printf("%d", n->data);
    return 0;
}

//反转链表
Node* reNode(Node* head)
{
    if(NULL == head)
        return head;
    Node* temp;
    Node* cur = head;
    Node* pre = NULL;
    while(cur){
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

//交换链表中的节点
Node* swapNode(Node* head) {
    if(NULL == head)
        return head;
    Node* vhead = new Node(0); //设置一个虚拟头结点
    vHead->next = head; //将虚拟头结点指向head，方便删除
    Node* cur = vhead;
    while(cur->next != NULL && cur->next->next != NULL) {
        Node* temp1= cur->next; //记录临时节点
        Node* temp2 = cur->next->next->next; //记录临时节点

        cur->next = cur->next->next;
        cur->next->next = temp1;
        cur->next->next->next = temp2;

        cur = cur->next->next; //cur移动两位，准备下一轮交换
    }
    return vHead->next;
}

//重排链表
void reorderNode(Node* head)
{
    if(NULL == head)
        return;
    Node* vec[64];
    Node* node = head;
    int n = 0;
    while (node != NULL) {
        vec[n++] = node;
        node = node->next;
    }
    int i = 0, j = n - 1;
    while (i < j) {
        vec[i]->next = vec[j];
        i++;
        if (i == j) {
            break;
        }
        vec[j]->next = vec[i];
        j--;
    }
    vec[i]->next = NULL;
    return;
}